package algorithm.linear;

/**
 * 单链表类
 */
public class SinglyLinkList<E> implements LList<E> {
    //头指针，指向单链表第一个结点
    protected Node<E> head;

    public SinglyLinkList() {
        this.head = null;
    }

    public SinglyLinkList(Node<E> head){
        this.head = head;
    }

    public boolean isEmpty() {
        return this.head == null;
    }

    public int length() {
        int i = 0;
        Node<E> p = this.head;
        while(p!=null) {
            i++;
            p = p.next;
        }
        return i;
    }

    public E get(int index) {
        if (this.head!=null && index>=0){
            int j = 0;
            Node<E> p = this.head;
            while (p!=null && j< index) {
                j++;
                p = p.next;
            }
            if (p != null) {
                return p.data;
            }
        }
        return null;
    }
    //已经存在的
    public E set(int index, E element) {
        if ( this.head!=null && index >= 0 && element!=null){
            int j = 0;
            Node<E> p = this.head;
            while(p!=null && j <index) {
                j++;
                p = p.next;
            }
            if (p!=null){
                E old = p.data;
                p.data = element;
                return old;
            }
        }
        return null;
    }
    //增加
    public boolean add(int index, E element) {
        if (element == null) {
            return false;
        }
        //头插入
        if (this.head==null || index <= 0 ){
            Node<E> q = new Node<E>(element);
            q.next = this.head;
            this.head = q;
        }
        else {
            int j = 0;
            Node<E> p = this.head;
            //找前一个
            while(p.next!=null && j<index-1) {
                j++;
                p = p.next;
            }
            //当前
            Node<E> q = new Node<E>(element);
            q.next = p.next;
            p.next = q;
        }
        return true;
    }

    public boolean add(E element) {
        return add(Integer.MAX_VALUE,element);
    }

    public E remove(int index) {
        E old = null;
        if (this.head!=null && index >= 0){
            old = this.head.data;
            this.head = this.head.next;
        } else {
            int j = 0;
            Node<E> p = this.head;
            while(p.next!=null && j<index -1 ){
                j++;
                p = p.next;
            }
            if (p.next!=null){
                old = p.next.data;
                //更换
                p.next = p.next.next;
            }
        }
        return old;
    }

    public void clear() {
        this.head = null;
    }

    public String toString() {
        String str = "(";
        Node<E> p = this.head;
        while(p!=null) {
            str += p.data.toString();
            p = p.next;
            if(p!=null){
                str += ",";
            }
        }
        return str+")";
    }

    /**
     * 从单链表start位置开始顺序查找指定对象
     * @param element
     * @param start
     * @return 若查找成功返回结点，否则null
     */
    public Node<E> search(E element, Node<E> start) {
        if(this.head == null || element == null)
            return null;
        Node<E> p = start;
        while (p!=null && !element.equals(p.data)) {
            p = p.next;
        }
        return p;
    }

    /**
     * 顺序查找指定对象
     * @param element
     * @return
     */
    public Node<E> search(E element){
        return  search(element,head);
    }
    /**
     * 查找是否包含指定对象
     */
    public boolean contain(E element){
        return this.search(element)!=null;
    }
    /**
     * 移除首次出现的指定对象
     */
    public boolean remove(E element) {
        if(this.head == null || element == null)
            return false;
        //头移除
        if (element.equals(this.head.data)){
            this.head = this.head.next;
            return true;
        }
        Node<E> front = this.head,p=front.next;//中间、尾删除
        while (p!=null && !element.equals(p.data)) {
            front = p;
            p = p.next;
        }
        if(p!=null){ //命中
            front.next = p.next;
            return true;
        }
        return false;
    }

}
